package leetcode;

import java.util.*;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-23 22:04
 **/
public class LeetCode437 {

    //前缀和
    public int pathSum(TreeNode root, int targetSum) {
        //key: 前缀和,value:前缀和出现的次数
        HashMap<Long, Integer> prefix = new HashMap<>();
        //防止寻找不含根节点的前缀和为targetSum的时候找不到
        prefix.put(0L, 1);

        return dfs(root, prefix, 0, targetSum);
    }

    public int dfs(TreeNode root, Map<Long, Integer> prefix, long curr, int targetSum) {
        if (root == null) {
            return 0;
        }

        int res = 0;
        curr += root.val;

        //获取到达当前节点的路径和为targetSum的个数
        res = prefix.getOrDefault(curr - targetSum, 0);
        //把当前切点的前缀和添加到map中,如果已存在当前前缀和的key,就+1
        prefix.put(curr, prefix.getOrDefault(curr, 0) + 1);
        //向下递归
        res += dfs(root.left, prefix, curr, targetSum);
        res += dfs(root.right, prefix, curr, targetSum);
        //回溯
        prefix.put(curr, prefix.getOrDefault(curr, 0) - 1);

        return res;
    }

    //递归
    /*public int pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }

        //返回以root为起点向下的路径中路径和为target的个数+递归root左子节点为起点路径和为target+递归右子节点为起点路径和为target的个数和.
        return dfs(root, targetSum) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);
    }

    int dfs(TreeNode root, int targetSum) {
        int res = 0;

        if (root == null) {
            return 0;
        }

        int val = targetSum - root.val;
        if (val == 0) {
            ++res;
        }

        return res + dfs(root.left, val) + dfs(root.right, val);
    }*/
}
